package com.zwy.Algorithm;

/*
分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，
再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，
原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。
分治法是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）等等。
 */
//使用分治实现快速排序
public class Quicksort {
    public static void main(String[] args) {
        Solution solution = new Quicksort().new Solution();
        int []arr={7,4,9,6,3,2,8,5,10};
        solution.sort(arr,0,arr.length-1);
        System.out.println(arr);
    }
    class Solution {
        public void sort(int [] arr,int start,int end) {
            if(start>=end)return;
            int low=start;
            int high=end;
            int sign=arr[low];
            int t;
            while(low<high){
                if(arr[high]>sign)high--;
                else {
                    if(arr[low]<sign)low++;
                    else {
                        t=arr[high];
                        arr[high]=arr[low];
                        arr[low]=t;
                    }
                }
            }
            arr[low]=sign;
            sort(arr,0,low-1);
            sort(arr,low+1,end);
        }

    }
}
